import com.sun.source.tree.Tree;

import java.util.Stack;

/*
 * @author zzr
 * @date: 2025/10/18  20:39
 * @description:
 * 二叉树的后序遍历非递归实现
 */
public class Demo35 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 在二叉树的后续遍历中，顺序为左右根。
     * 核心难点在于：必须完全保证右子树全部遍历完成之后，才能访问根节点
     * 本方法通过 prev 变量，记录了上一个访问的节点，配合栈来判断右子树是否完全遍历
     * 从而实现正确的后续遍历
     * 栈：保存已遍历左子树，但未确定右子树是否遍历完的根节点
     * prev：记录上一个已经访问过的节点，用于判断当前栈顶节点的右子树是否已经遍历
     * 双重循环：内层循环负责“深入左子树并压栈”
     *          外层循环通过栈和 prev 控制右子树遍历和根节点访问的顺序
     * @param root
     */
    public void postOrderNor(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode prev = null;

        // 外层循环：cur 不为空，或栈不为空（还有未处理节点）
        while (cur != null || !stack.isEmpty()) {
            // 内层循环，一路向左压栈（先处理左子树）
            stack.push(cur);
            cur = cur.left;
        }
        // 查看栈顶节点，但不要直接弹出（需要判断右子树是否遍历）
        top = stack.peek();

        // 判断是否可以访问当前栈顶节点
        // 1. 右子树为空
        // 2. 右子树已经访问过了（prev 记录了右子树）
        if (top.right == null || top.right == prev) {
            // 弹出并访问当前节点
            stack.pop();
            System.out.println(top.val + " ");
            // 注意！！用 prev 来表示已经访问过该节点
            prev = top;
        } else {
            // 右子树还未遍历完毕，转向处理右子树
            cur = top.right;
        }
    }
}
